class Solution {
public:
    vector<int> ret;
    unordered_map<int,unordered_set<TreeNode*> > edges;
                                        
    void change(TreeNode* root){
        if(!root) return;
        
        if(root->left){
            edges[root->val].insert(root->left);
            edges[root->left->val].insert(root);
        }
        
        if(root->right){
            edges[root->val].insert(root->right);
            edges[root->right->val].insert(root);
          
        }
        
        change(root->left);
        change(root->right);
        
    }     
                                        
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) { 
        if(!target) return {};
        int t = target->val;
        if(k == 0) return {t};
        
        change(root);
        if(!edges.count(t)) return {};
        
        
        queue<pair<int,int> > q;
        q.emplace(t,0);
        
        unordered_set<TreeNode*> vis;
        vis.insert(target);
       
        while(!q.empty()){
            auto [u,step] = q.front();
            q.pop();
            
            for(auto& v : edges[u]){
            
                if(!vis.count(v) && step < k){
                    q.emplace(v->val,step+1);
                    
                    vis.insert(v);
                    
                    if(step == k-1){
                        ret.push_back(v->val);
                    }
                }
            }
        }
        return ret;
    }
};
